package com.mango.leet.code.middle;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: mango
 * @Date: 2024/3/23 23:47
 */
public class LC47 {
    List<List<Integer>> resultList = new ArrayList<>();
    LinkedList<Integer> trackList = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        trackback(nums, nums.length);
        return resultList;
    }

    private void trackback(int[] nums, int size) {
        if (trackList.size() == size) {
            ArrayList<Integer> list = new ArrayList<>(trackList);
            if (!resultList.contains(list)) {
                resultList.add(list);
            }
            return ;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            int num = nums[i];
            trackList.addLast(num);
            used[i] = true;
            trackback(nums, size);
            trackList.removeLast();
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        LC47 r = new LC47();
        System.out.println(r.permuteUnique(new int[]{1,2,3}));
        //System.out.println(r.permuteUnique(new int[]{1,1,2}));
    }
}
